﻿\subsection{Антисловари абелево $\beta$-свободных языков}
\label{subsection:abelian-algo}

Пусть $\beta >1$~--- вещественное число.
Чтобы оценить индекс роста абелево $\beta$-свободного языка с помощью
метода, изложенного в разделе~\ref{section:theory}, нам необходимо
построить конечное приближение антисловаря этого языка. Мы будем строить
все минимальные (относительно взятия подслов) запрещённые слова языка,
длина которых не превосходит $R$. Следующая
лемма очевидно следует из определений дробных абелевых степеней.

\begin{lmm} \label{sym}
Если слово $w \in \Sigma^{*}$ является слабой (полустрогой, строгой) абелевой
$\beta$-степенью, а $\phi$~--- перестановка букв $\Sigma$, то
$\phi(w)$ также является слабой (соответственно, полустрогой, строгой) абелевой $\beta$-степенью.
\end{lmm}

Из леммы~\ref{sym} следует, что абелево $\beta$-свободные языки являются
симметричными, а значит, мы можем воспользоваться приёмом, описанным в разделе~\ref{section:theory},
и находить только лексикографически минимальные слова (\textit{лексмин-слова}) в своих
классах эквивалентности. Это позволит нам сократить размер антисловаря
примерно в $|\Sigma|!$ раз.

В процессе алгоритма мы будем заносить найденные минимальные запрещённые слова
в бор. Мы будем хранить всевозможные корни лексикографически минимальных слов
во вспомогательной очереди $Q$, перебирая корни в порядке возрастания длины.
Эти корни должны быть минимальными в своём классе эквивалентности. Для удобства, для
каждого слова в очереди мы будем хранить количество различных букв в этом слове.
Для каждого корня $r$ мы будем строить все минимальные запрещённые слова с этим
корнем, добавлять их в бор, после чего пытаться приписать всевозможные буквы из
$\Sigma$ к корню и добавить новый корень в очередь. Затем мы извлечём из очереди
очередной корень, и будем продолжать алгоритм до тех пор, пока не обработаем все
корни длины не более $R$ (см. процедуру ~\textsc{iterate}). Мы считаем, что
$\Sigma = \{1,\ldots,k\}$. \textsc{build}~--- это рекурсивная процедура, описанная ниже
на стр.\,\pageref{pr2}. В результате вызова \textsc{build} в строке~4,
в бор добавляются все запрещённые лексмин-слова с корнем~$r$.

\noindent\textsc{iterate} (внешний цикл).
\texttt{\begin{tabbing}
01. $Q \leftarrow ('1';1)$\\
02. пока \= $Q \neq \emptyset$ \\
03. \> $(r;t) \leftarrow Q$\\
04. \> \textsc{build}$(r,r,\vec{p}(r))$\\
05. \> если \= $|r| < R$\\
06. \>\> для \= $c \le t$, таких что у $rc$ нет запрещённых суффиксов\\
07. \>\>\> $Q \leftarrow (rc;t)$\\
08. \>\> если \= $t < k$\\
09. \>\>\> $Q \leftarrow (r(t{+}1);t{+}1)$\\
10. конец цикла\\
\end{tabbing}}
Построение всех минимальных запрещённых слов с данным корнем занимает много времени,
поскольку количество этих слов может быть очень велико. Зависимость их длин от длины
корня также нетривиальна, как видно из следующей леммы.

\begin{lmm} \label{lens}
Если $w \in \Sigma^{*}$~--- минимальное запрещённое слово для абелево $\beta$-свободного
языка, а длина его корня равна $R$, то:
\begin{itemize}
\item[(1)] $|w| = \lceil R \cdot \beta \rceil$ для слабых абелевых степеней,
\item[(2)] $\lceil R \cdot \beta \rceil \le |w| \le R \cdot \lceil \beta \rceil$
для строгих и полустрогих абелевых степеней, и в общем случае эти оценки точные.
\end{itemize}
\end{lmm} 

\begin{proof}
Минимальное запрещённое слово для абелево $\beta$-свободного языка является как минимум
абелевой $\beta$-степенью, поэтому нижняя оценка на $|w|$ следует из определений. Чтобы доказать
(1), заметим, что каждый префикс слабой абелевой степени также является слабой абелевой степенью с тем
же корнем. Поэтому, если длина $w$ превосходит $\lceil R \cdot \beta \rceil$, у
$w$ будет собственный запрещённый префикс. Это замечание также доказывает верхнюю оценку
в (2) ввиду замечания~\ref{abel1}\,(1). 
В случае строгих и полустрогих абелевых степеней ситуация осложняется тем, что 
не все их префиксы являются абелевыми степенями. Так, абелев квадрат $abcde\,bdaec$ длины
$10$ является также минимальным запрещённым словом для строгого (и полустрогого) абелево
$(7/5)$-свободного языка, что можно проверить вручную. Этот пример также показывает, что
верхняя оценка в (2) является точной.
\end{proof}

Мы строим запрещённые лексмин-слова с данным корнем рекурсивно, приписывая по
одной букве к текущему слову пока не выполнится одно из трёх условий:
текущее слово станет запрещённым лексмин-словом, текущее слово станет слишком
длинным, у текущего слова появится запрещённый собственный суффикс. На каждом шаге
мы поддерживаем вектор неиспользованных букв $\vec p$. Когда мы дописываем букву
$c$ к слову, мы уменьшаем соответствующую компоненту $[\vec p]_c$ на единицу. При этом,
если, дописав букву, мы закончили дописывать анаграмму корня ($\vec p$ стал нулевым),
то мы заново присваиваем $\vec p$ частотный вектор корня. Формальное описание этого процесса
приведено в процедуре~\textsc{build}, аргументами которой является текущее слово $w$, корень
$r$ и текущий вектор неиспользованных букв $\vec p$. \textsc{is\_abelian}~--- это процедура,
проверяющая, является ли $w$ (слабой, полустрогой, строгой) абелевой степенью с корнем~$r$.

\noindent\textsc{build}($w,r, \vec p$) (построение запрещённых слов). \label{pr2}
\texttt{\begin{tabbing}
01. если \= \textsc{is\_abelian}($w,r$)\\
02. \> если \= $|w|$ удовлетворяет лемме \ref{lens}\\
03. \>\> добавить $w$ в бор\\
04. \> завершить процедуру\\
05. если \= $|w|$ равно верхней границе из леммы \ref{lens}\\
06. \> завершить процедуру\\
07. если \= $|w| \mod |r| = 0$\\
08. \> $\vec p \leftarrow \vec p(r)$\\
09. для \= всех $c$, таких что $[\vec p]_c > 0$\\
10. \> $u \leftarrow wc$\\
11. \> $\vec q \leftarrow \vec p$\\
12. \> $[\vec q]_c \leftarrow [\vec q]_c - 1$\\
13. \> если \= $u$ не имеет запрещённых собственных суффиксов\\
14. \> \> \textsc{build}($u,r, \vec q$)\\
15. завершить процедуру\\
\end{tabbing}}
\vspace*{-5mm}

Если выполняются условия в строках 1 и 2, то слово $w$ является абелевой степенью
с корнем $r$ и абелевой экспонентой не меньше $\beta$. В нём нет запрещённых собственных подслов,
поскольку (а) $r$ является абелево $\beta$-свободным словом по построению, см. процедуру
\textsc{iterate}, и (б) в течение рекурсивного построения мы проверяли условие в строке 13 для
каждого префикса $w$ длины больше $|r|$. Поэтому $w$ в самом деле является минимальным запрещённым
словом, и операция в строке 3 справедлива.

Мы можем поддерживать частотные векторы всех префиксов $w$. Следовательно, мы можем вычислять
частотный вектор любого подслова этого слова, вычитая частотные векторы соответствующих префиксов.
Этого достаточно, чтобы реализовать процедуру \textsc{is\_abelian}
за константное время для любого из трёх определений дробной абелевой степени, считая
$\lfloor\beta\rfloor$ и $|\Sigma|$ константами.

Наконец, мы должны эффективно проверять условие в строке 13. Следующие леммы понадобятся нам
в частных случаях:

\begin{lmm} \label{integral}
Если $\beta$~--- целое число, слово $w \in \Sigma^{*}$ является абелевой $\beta$-степенью,
то развёрнутое $w$ также является абелевой $\beta$-степенью.
\end{lmm}

\begin{lmm} \label{weak1}
Пусть $u, v, w \in \Sigma^{*}$, $u, v$~--- суффиксы $w$, $\bar{u}$ ($\bar{v}$)~---
кратчайший суффикс $w$, являющийся нетривиальной слабой абелевой степенью с хвостом
$u$ (соответственно, $v$). Если $|u| < |v|$, то $|\bar{u}| \le |\bar{v}|$.
\end{lmm}

\begin{proof}
Пусть $\bar{v} = \hat{v} v$. Тогда $\vec p(\hat{v}) \ge \vec p(v) \ge \vec p(u)$. Это значит, что
$\bar{v}$ является слабой абелевой степенью с хвостом $u$ по определению.
Но $\bar{u}$~--- кратчайший суффикс $w$ с таким свойством, поэтому $|\bar{u}| \le |\bar{v}|$.
\end{proof}

Теперь мы можем сформулировать главную лемму, оценивающую время работы процедуры, проверяющей
наличие запрещённых суффиксов. Мы считаем $|\Sigma|$ константой.

\begin{lmm}
Пусть $w \in \Sigma^{*}$, $|w| = n$, $\beta > 1$. По нашему алгоритму, мы можем проверить, есть
ли у $w$ суффикс с абелевой экспонентой не меньше~$\beta$:
\begin{itemize}
\item[(1)] за время $O(n)$, если $\beta$ целое или если $\beta < 2$ и мы рассматриваем слабые абелевы степени;
\item[(2)] за время $O(n^2)$ во всех остальных случаях.
\end{itemize}
\end{lmm}

\begin{proof}
Если $\beta$ целое, то на момент рассмотрения $w$ все более короткие запрещённые слова
уже добавлены в бор. По лемме~\ref{integral}, мы можем проверить префиксы развёрнутого слова $w$
вместо суффиксов $w$. Поэтому, мы читаем слово $w$ справа налево и <<на лету>> заменяем
читаемое слово на его симметричное ему лексмин-слово. Для этого достаточно хранить образы
заменённых букв в массиве константного размера. Если образ очередной буквы ещё не определён,
он устанавливается равным максимальному на данный момент образу, увеличенному на единицу.
Полученное лексмин-слово далее рассматривается как вход для построенного на данный момент бора.
Если при чтении слова в боре достигается терминальное состояние, это означает, что найден
запрещённый префикс. Если такое состояние не достигается, то во входном слове нет запрещённых
префиксов. Эта проверка также занимает линейное время, что доказывает утверждение для целых степеней.

Предположим, что $\beta$ не целое, а у $w$ есть запрещённый собственный суффикс. Тогда длина
этого суффикса определяется длинами его корня и хвоста. Переберём все возможные значения
этих длин (каждая из них не превосходит $n / \lfloor\beta\rfloor$) и проверим, действительно
ли соответствующий суффикс является абелевой степенью с достаточно большой экспонентой.
Эта проверка осуществляется за константное время с помощью описанной ранее процедуры
\textsc{is\_abelian}, что даёт нам общее квадратичное время. Если $1 < \beta < 2$ и
мы рассматриваем слабые абелевы степени, то по лемме~\ref{weak1} запрещённый
суффикс не может стать короче, если его хвост стал длиннее (заметим, что лемма~\ref{weak1}
рассматривает только \textit{кратчайшие} абелевы степени с данным хвостом). Значит,
в этом случае процедуру можно реализовать за линейное время.
\end{proof}

